package com.dmall.play.interview.chapter09;

public class Leetcode64V1 {

    private int minTotal = Integer.MAX_VALUE;
    private int row, col;

    public int minPathSum(int[][] grid) {
        row = grid.length;
        col = grid[0].length;
        backTrack(grid, 0, 0, 0);
        return minTotal;
    }

    private void backTrack(int[][] grid, int row, int col, int total) {
        if (row == this.row - 1 && col == this.col - 1) {
            minTotal = Math.min(minTotal, total + grid[row][col]);
            return;
        }
        total += grid[row][col];
        if (row < this.row - 1) {
            backTrack(grid, row + 1, col, total);
        }
        if (col < this.col - 1) {
            backTrack(grid, row, col + 1, total);
        }
    }

    public static void main(String[] args) {
        Leetcode64V1 leetcode64 = new Leetcode64V1();
        int[][] grid = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
        //int[][] grid = {{1, 2}, {1, 1}};
        System.out.println(leetcode64.minPathSum(grid));
    }
}
